class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        # dp[i][j] 表示数组范围 (i, j) 可以得到的最大硬币个数
        n = len(nums)
        nums_ = [1] + [x for x in nums] + [1]
        dp = [[0] * (n + 2) for _ in range(n + 2)]
        print(dp)
        for i in range(n - 1, -1, -1):
            # 正序枚举右边界，右边界最大为n+1
            for j in range(i + 2, n + 2):
                # 枚举区间中每一个元素作为区间中最后去除的元素，得到区间(i,j)可以获得的最大硬币数
                for k in range(i + 1, j):
                    # k作为去掉的元素，得到的硬币数为nums[i]*nums[k]*nums[j]，索引越界则值为1
                    # 而剩下的部分就是子问题，区间(i,k)和(k,j)可以获得的最大硬币数
                    dp[i][j] = max(dp[i][j], dp[i][k] + nums_[i] * nums_[k] * nums_[j] + dp[k][j])    
        print(dp)
        return dp[0][n + 1]